/LMAR=0/XLINE=3/FONT#0=BAXL30[FNT,CLT]/FONT#1=BAXM30/FONT#2=BAXB30[FNT,CLT]/FONT#5=NGR25/FONT#3=SUB/FONT#4=SUP/FONT#7=SYMB30[FNT,CLT]

␈↓ ↓H␈↓␈↓ ∧+COMPUTER SCIENCE DEPARTMENT
␈↓ ↓H␈↓␈↓ ¬πSTANFORD UNIVERSITY
␈↓ ↓H␈↓CS206  ␈↓ βZCOMPUTING WITH SYMBOLIC EXPRESSIONS  ␈↓ 
SPRING 1978

␈↓ ↓H␈↓α␈↓ ¬HMIDTERM EXAM

␈↓ ↓H␈↓        Write definitions for the following functions or predicates.

␈↓ ↓H␈↓        You␈αmay␈αuse␈αany␈α
books␈αor␈αnotes␈αthat␈αyou␈α
wish␈αon␈αthis␈αtest.␈α
 You␈αmay␈αuse␈αeither␈αexternal␈α
or
␈↓ ↓H␈↓internal notation for your definitions.

␈↓ ↓H␈↓1.␈α∞The␈α∞␈↓↓depth␈↓␈α∞of␈α∞an␈α∞S-expression␈α∞is␈α∞given␈α∞by␈α
the␈α∞length␈α∞of␈α∞the␈α∞longest␈α∞path␈α∞to␈α∞an␈α∞atom.␈α
 Thus
␈↓ ↓H␈↓␈↓ αλ␈↓↓depth[␈↓¬A␈↓↓]=0␈↓ and ␈↓↓depth[␈↓¬(((A.B).C).D)␈↓↓]=3␈↓.

␈↓ ↓H␈↓2.␈α␈↓↓balanced[x]␈↓␈αis␈αtrue␈αif␈αand␈αonly␈αif␈αthe␈αS-expression␈αis␈αbalanced.␈α We␈αsay␈αthat␈αan␈αS-expression␈αis
␈↓ ↓H␈↓␈↓ αλbalanced␈αif␈αit␈αis␈αan␈αatom␈α
or␈αif␈α␈↓↓depth[␈↓αa|␈↓↓x]␈↓␈αand␈α␈↓↓depth[␈↓αd|␈↓↓x]␈↓␈αdiffer␈α
by␈αat␈αmost␈α1␈αand␈α␈↓αa|␈↓␈↓↓x␈↓␈α
and␈α␈↓αd|␈↓␈↓↓x␈↓
␈↓ ↓H␈↓␈↓ αλare both balanced.  Thus ␈↓↓balanced[␈↓¬((A.B).C)␈↓↓]␈↓ is true but ␈↓↓balanced[␈↓¬(((A.B).C).D)␈↓↓]␈↓ is false.

␈↓ ↓H␈↓3.  Let ␈↓↓g␈↓ be an undirected graph represented as a list of lists as described in Chapter I.

␈↓ ↓H␈↓    3.1.␈α ␈↓↓delete_vertex[v,g]␈↓␈α returns␈αa␈αgraph␈α␈↓↓g1␈↓␈αwith␈αvertices␈αthose␈αof␈α␈↓↓g␈↓␈αomitting␈α␈↓↓v,␈↓␈αand␈αedges␈αthe
␈↓ ↓H␈↓␈↓ αλsame as ␈↓↓g␈↓ omitting those connecting ␈↓↓v␈↓ to another vertex.

␈↓ ↓H␈↓    3.2.␈α ␈↓↓complement[g]␈↓␈α returns␈αa␈αgraph␈α␈↓↓g1␈↓␈αwith␈αvertices␈α
the␈αsame␈αas␈α␈↓↓g,␈↓␈αbut␈αvertices␈α␈↓↓v␈↓␈αand␈α
␈↓↓w␈↓␈αare
␈↓ ↓H␈↓␈↓ αλjoined by an edge in ␈↓↓g1␈↓ if and only if they are not joined by an edge in ␈↓↓g.␈↓

␈↓ ↓H␈↓        For example if ␈↓↓g␈↓ is given by ␈↓¬((A B D) (B C D A) (C D B) (D A B C))␈↓ then we have:

␈↓ ↓H␈↓                ␈↓↓delete_vertex[␈↓¬A␈↓↓,g]=␈↓␈↓¬((B C D) (C D B) (D B C))␈↓
␈↓ ↓H␈↓                ␈↓↓         complement[g]=␈↓␈↓¬((A C) (B) (D) (C A))␈↓.

␈↓ ↓H␈↓4.  Consider arithmetic expressions as represented in Ch I. Namely an expression is

␈↓ ↓H␈↓        (i) a number (satisfies ␈↓↓numberp),␈↓
␈↓ ↓H␈↓        (ii) a variable (not a number and satisfies ␈↓αat␈↓),
␈↓ ↓H␈↓        (iii) a sum : ␈↓¬PLUS ␈↓. < list of expressions > or
␈↓ ↓H␈↓        (iv) a product : ␈↓¬TIMES ␈↓. < list of expressions >.

␈↓ ↓H␈↓    (For simplicity, assume the sum and product lists always have at least 2 elements.)

␈↓ ↓H␈↓        The␈α∂function␈α∂␈↓↓sop␈↓␈α∂converts␈α∂such␈α∂expressions␈α∂into␈α∂sum␈α∂of␈α∂products␈α∂form,␈α∂eg.␈α⊂the␈α∂resulting
␈↓ ↓H␈↓␈↓ αλexpression␈α⊗is␈α⊗either␈α⊗a␈α∃monomial␈α⊗or␈α⊗a␈α⊗sum␈α⊗of␈α∃monomial␈α⊗terms␈α⊗which␈α⊗has␈α⊗the␈α∃form
␈↓ ↓H␈↓␈↓ αλ␈↓¬PLUS␈↓ . <list of monomials>.␈α A␈αmonomial␈αis␈αeither␈αa␈α
number,␈αa␈αvariable,␈αor␈αa␈αproduct␈α
of␈αthe
␈↓ ↓H␈↓␈↓ αλform ␈↓¬TIMES␈↓ . < list of numbers or variables >.  Thus,
␈↓ ↓H␈↓                ␈↓↓sop[␈↓¬(TIMES (TIMES X 3) (PLUS Y Z) (PLUS Y 1))␈↓↓]=␈↓
␈↓ ↓H␈↓                        ␈↓¬(PLUS (TIMES X 3 Y Y) (TIMES X 3 Y 1) (TIMES X 3 Z Y) (TIMES X 3 Z 1))␈↓.

␈↓ ↓H␈↓        Notice that simplification is not required.